package list

import C "gitee.com/ljfirst/algo-go-sdk/common/constant"

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/6 23:31
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 * */
type LastKRecursion struct {
}

func (m *LastKRecursion) FindMethod(root *Node, k int) *Node {
	if root == nil || k <= 0 {
		return nil
	}
	_, want := m.roll(root, k)
	return want
}

func (m *LastKRecursion) roll(root *Node, k int) (int, *Node) {
	if root == nil {
		return 0, nil
	}
	level, want := m.roll(root.Next, k)
	if level == k {
		return level, want
	}
	return level + 1, root
}

func (m *LastKRecursion) Delete(root *Node, k int) *Node {
	if root == nil || k <= 0 {
		return root
	}
	level, _ := m.rollDel(root, k)
	if level == k {
		root = root.Next // attention指针：输入的root此时指针地址发生变更，需要显式输出，或者包在struct内部来保证指针地址更换后，引用对象不变
	}
	return root
}

func (m *LastKRecursion) rollDel(root *Node, k int) (int, *Node) {
	if root.Next == nil {
		return 1, root
	}
	level, want := m.rollDel(root.Next, k)
	level++
	if level-1 == k {
		root.Next = want.Next
		return level, want
	}
	return level, root
}

func (m *LastKRecursion) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.List},
		Desc: &C.Desc{
			Name:   "LastKRecursion",
			NameCn: "倒数第K个元素-递归写法",
		},
	}
}
